

#include <sudoku.h>

int _sdk_depth;

sudoku *_sdk_do_rec_solve(sudoku *sdk){

  _sdk_depth++;

  if (sdk_solve(sdk)){
    //fprintf(stderr, "Sudoku solved: depth=%d\n", _sdk_depth);
    return sdk_copy_sudoku(sdk);
  }
  
  if (!sdk_solvable(sdk)){
    _sdk_depth--;
    return NULL;
  }
  
  sdk_square *branch = _sdk_locate_branch_square(sdk);

  int i;
  int len = sdk_list_length(&branch->pos);

  for ( i = 0; i < len; i++){

    int guess = sdk_list_get_elem(&branch->pos, i)->num;
    sudoku *copy = sdk_copy_sudoku(sdk);

    SDK_SET_VAL(copy, branch->row, branch->col, guess);
    sdk_update_lists(copy);

    sudoku *tmp = _sdk_do_rec_solve(copy);
    if (tmp){
      return tmp;
    }
    sdk_free_sudoku(copy); // FIXME: This is a memory leak.
  }

  _sdk_depth--;
  return NULL;

}

sudoku *_sdk_rec_solve(sudoku *sdk){

  /* First, try and use the regular solver against the sudoku */
  if (sdk_solve(sdk)){
    return sdk_copy_sudoku(sdk);
  }

  _sdk_depth = 0;

  /* If it didnt solve then we have to start brute forcing it. */
  sudoku *solved = _sdk_do_rec_solve(sdk);

  /* At this point the sudoku is solved. */
  return solved;
  
}
